package _滑动窗口;

import java.util.*;

public class _window {
    //3 :无重复字符的最长子串 https://leetcode.cn/problems/longest-substring-without-repeating-characters/
    // “abcabcbb” 3 3


    // 209：长度最小的子数组：https://leetcode.cn/problems/minimum-size-subarray-sum/
    public int minSubArrayLen(int target, int[] nums) {
        return 0;
    }

    public int lengthOfLongestSubstring(String s) {
        HashSet<Character> set = new HashSet<>();
        int ans = 0;
        for (int l = 0, r = 0; r < s.length(); r++) {
            char c = s.charAt(r);
            while (set.contains(c)) { // 有重复，缩短左边界
                set.remove(s.charAt(l));
                l++;
            }
            set.add(c);
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }

    // 438:找到字符串中所有字母的异位词 https://leetcode.cn/problems/find-all-anagrams-in-a-string/
    public List<Integer> findAnagrams(String s, String p) {
        int sl = s.length(), pl = p.length();
        if (sl < pl) return new ArrayList<>();
        // 用数组来模拟哈希表，记录 窗口 和 p 每个字符的数量
        int[] win = new int[26];
        int[] pc = new int[26];
        ArrayList<Integer> ans = new ArrayList<>();
        // 先按照p遍历一遍
        for (int i = 0; i < pl; i++) {
            win[s.charAt(i) - 'a']++;
            pc[p.charAt(i) - 'a']++;
        }
        if (Arrays.equals(win, pc)) {
            ans.add(0);
        }
        // 模拟固定长度的窗口滑动
        for (int l = 0; l < sl - pl; l++) {
            win[s.charAt(l) - 'a']--;
            win[s.charAt(l + pl) - 'a']++;
            if (Arrays.equals(win, pc)) {
                ans.add(l + 1);
            }
        }
        return ans;
    }

    // 242：有效字母的异位词 https://leetcode.cn/problems/valid-anagram/description/
    public boolean isAnagram(String s, String t) {
        int[] record = new int[26]; //有限组合，用数组模拟 hash

        for (int i = 0; i < s.length(); i++) {
            record[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < t.length(); i++) {
            record[t.charAt(i) - 'a']--;
        }
        for (int count : record) {
            if (count != 0) {
                return false;
            }
        }
        return true;
    }

    // 567：字符串的排列 https://leetcode.cn/problems/permutation-in-string/
    public boolean checkInclusion(String s1, String s2) {
        int sl = s2.length(), pl = s1.length();
        if (sl < pl) return false;
        // 用数组来模拟哈希表，记录 窗口 和 p 每个字符的数量
        int[] win = new int[26];
        int[] pc = new int[26];
        // 先按照p遍历一遍
        for (int i = 0; i < pl; i++) {
            win[s2.charAt(i) - 'a']++;
            pc[s1.charAt(i) - 'a']++;
        }
        if (Arrays.equals(win, pc)) {
            return true;
        }
        // 模拟窗口滑动
        for (int i = 0; i < sl - pl; i++) {
            win[s2.charAt(i) - 'a']--;
            win[s2.charAt(i + pl) - 'a']++;
            if (Arrays.equals(win, pc)) {
                return true;
            }
        }
        return false;
    }
    // 76：最小覆盖字串：https://leetcode.cn/problems/minimum-window-substring/description/

    // 239：滑动窗口最大值：https://leetcode.cn/problems/sliding-window-maximum/description/
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0 || k == 0) return new int[0];

        int n = nums.length;
        int[] res = new int[n - k + 1];
        Deque<Integer> deque = new LinkedList<>(); // 存索引

        for (int i = 0; i < n; i++) {
            // 1. 移除不在窗口的元素
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }
            // 2. 移除所有比当前元素小的元素（它们不可能成为最大值）
            while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
                deque.pollLast();
            }
            // 3. 加入当前元素索引
            deque.offerLast(i);
            // 4. 从第一个完整窗口开始记录结果
            if (i >= k - 1) {
                res[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        return res;
    }

    // 674：最长连续递增子序列：https://leetcode.cn/problems/longest-continuous-increasing-subsequence/description/
    public int findLengthOfLCIS(int[] nums) {
        if (nums.length == 0) return 0;

        int maxLen = 1;
        int start = 0;

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) {
                maxLen = Math.max(maxLen, i - start + 1);
            } else {
                start = i;  // 重置起始点
            }
        }
        return maxLen;
    }


}
